
    /********************************************************/
    /*                                                      */
    /*                                                      */
    /*         Copyright (C), 1993  SEIKO EPSON Corp.       */
    /*         ALL RIGHTS RESERVED                          */
    /*                                                      */
    /*                                                      */
    /*  file name : qsort.c                                 */
    /*                                                      */
    /*  Revision history                                    */
    /*      93/12/17    first release       S.Akaiwa        */
    /*      97/2/20	modified	    T.Katahira	    */
    /*			change function declaration	    */
    /*					to the ANSI style   */
    /*                                                      */
    /********************************************************/

#ifdef      UNIX
#include    <stdio.h>
#include    "stdlib.h"
#else
#include    <stdlib.h>
#endif

static void	swap (unsigned char *, unsigned char *, int );

void
qsort(void * vpBase, size_t tdCnt, size_t tdSiz, fn_t * fnCmp)

    /********************************************************/
    /*                                                      */
    /*  The qsort function sorts array pointed to by vpBase.*/
    /*  The number of element in the array is specified by  */
    /*  tdCnt, and size of a element is specified by tdSiz. */ 
    /*  The comparison function pointer to by fnCmp is      */
    /*  called with 2 arguments. This function must return  */
    /*  an integer less than, equal to, or greater than     */
    /*  zero if the first argument is considered to be      */
    /*  respectively less than, equal to, or greater than   */
    /*  the second argument.                                */
    /*                                                      */
    /*      RETURN  Nothing                                 */
    /*                                                      */
    /********************************************************/

    /* void    * vpBase  ;                 pointer to array */
    /* size_t    tdSiz   ;                size of a element */
    /* size_t    tdCnt   ;                number of element */
    /* fn_t    * fnCmp   ;   pointer to comparison function */ 
    {

     char   * vpCmpPtr;   /* pointer to comparision element */
     char   * vpSwpPtr;          /* pointer to swap element */ 
     int      iLowerCnt;             /* lower element count */
     int      iHigherCnt;            /* higher element count */
     
     if(tdCnt <= 1){                      /* single element */
        return;                            /* nothing to do */
     }
     
     if(tdCnt == 2){                          /* 2 elements */
                                       /* compare 2 element */  
        if((fnCmp(vpBase, (char *)vpBase + tdSiz)) > 0){ 
                                     /* element1 > element2 */
           swap(vpBase, (char *)vpBase + tdSiz, tdSiz);    
        }
        return;
     }
             /* select comparative object, and 
                    swap comparative object for top element */ 
     swap(vpBase, (char *)vpBase + (tdCnt / 2 * tdSiz), tdSiz);
                  /* set comparision pointer to 2nd element */ 
     vpCmpPtr = (char *)vpBase + tdSiz;
                         /* set swap ponter to last element */
     vpSwpPtr = (char *)vpBase + (tdSiz * (tdCnt -1));
    
     iLowerCnt = 0; /* clear lower and higher element count */
     iHigherCnt = 0;
                            /* divide higher and lower data */ 
     while(vpCmpPtr <= vpSwpPtr){
        if(fnCmp(vpBase, vpCmpPtr) < 0){

                   /* element1(vpBase) < element2(vpCmpPtr) */
           swap(vpCmpPtr, vpSwpPtr, tdSiz);         /* swap */
         
                         /* move vpSwpPtr to before element */
           vpSwpPtr = vpSwpPtr - tdSiz;
           iHigherCnt++;              /* higher counter + 1 */
        }
        else {
                           /* move vpCmpPtr to next element */
           vpCmpPtr = vpCmpPtr + tdSiz;
           iLowerCnt++;                /* lower counter + 1 */
        }
     }
                   /* swap comparative object and 
                             element pointed to by vpSwpPtr */
     swap(vpBase, vpSwpPtr, tdSiz); 

                                    /* sorts lower elements */
     qsort(vpBase, iLowerCnt, tdSiz, fnCmp);

                                   /* sorts higher elements */
     qsort(vpCmpPtr, iHigherCnt, tdSiz, fnCmp);
    }
    

static void
swap(unsigned char * ucSrcPtr, unsigned char * ucDstPtr, int tdSiz)
    /********************************************************/
    /*                                                      */
    /*  The swap function swaps element pointed to by       */
    /*  ucSrcPtr for pointed to by ucDstPtr.                */
    /*  The size of element is specified by tdSiz.          */
    /*  This function is called by only qsort function.     */
    /*                                                      */
    /*      RETURN  Nothing                                 */
    /*                                                      */
    /********************************************************/

    /* unsigned char  *ucSrcPtr;  pointer to source element */
    /* unsigned char  *ucDstPtr; ptr to destination element */
    /* int             tdSiz    ;                swap count */
    {

     size_t        tdOfst   ;     /* offset in swap element */  
     unsigned char ucDat    ;   /* temporary data save area */

     tdOfst = 0;

     while(tdOfst < tdSiz){      /* swap a data until tdSiz */
        ucDat = (unsigned char)ucSrcPtr[tdOfst];
        ucSrcPtr[tdOfst] = ucDstPtr[tdOfst];
        ucDstPtr[tdOfst] = ucDat;
        tdOfst++;
     }
    
      return;                                    /* success */
    }

